package pers.qianyu.month_202012.date_20201221;

import org.junit.*;

/**
 * [模糊]
 * 134. 加油站
 * https://leetcode-cn.com/problems/gas-station/
 *
 * @author mizzle rain
 * @date 2020-12-21 15:56
 */
public class CanCompleteCircuit {
    // 暴力解法
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        int res = -1;
        for (int i = 0; i < len; i++) {
            int cur = i, size = 0, count = 0;
            while (count <= len) {
                size += gas[cur];
                if (size < cost[cur]) {
                    break;
                } else {
                    size -= cost[cur];
                }
                cur = (cur + 1) % len;
                count++;
            }
            if (count == len + 1) {
                // 如果循环执行了 len + 1 次，说明跑完了一圈
                res = i;
            }
        }
        return res;
    }

    // 另一种解法
    public int canCompleteCircuit2(int[] gas, int[] cost) {
        int len = gas.length;
        int sumRest = 0, min = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            int rest = gas[i] - cost[i];
            sumRest += rest;
            min = Math.min(sumRest, min);
        }
        // 两种特殊情况
        // - 总加油量小于总用油量，一定不能跑一圈
        // - 每次加油量都大于等于用油量，那么从 0 开始走即可
        if (sumRest < 0) {
            return -1;
        }
        if (min >= 0) {
            return 0;
        }
        for (int i = len - 1; i >= 0; i--) {
            int rest = gas[i] - cost[i];
            min += rest;
            if (min >= 0) {
                return i;
            }
        }
        return -1;
    }

    // 贪心算法
    public int canCompleteCircuit3(int[] gas, int[] cost) {
        int totalSum = 0, curSum = 0, start = 0;
        int len = gas.length;
        for (int i = 0; i < len; i++) {
            int rest = gas[i] - cost[i];
            totalSum += rest;
            curSum += rest;
            if (curSum < 0) {
                curSum = 0;
                start = i + 1;
            }
        }
        if (totalSum < 0) {
            return -1;
        }
        return start;
    }

    @Test
    public void test1() {
        int[] gas = {1, 2, 3, 4, 5};
        int[] cost = {3, 4, 5, 1, 2};
        int result = new CanCompleteCircuit().canCompleteCircuit(gas, cost);
        Assert.assertEquals(result, 3);
    }

    @Test
    public void test2() {
        int[] gas = {2, 3, 4};
        int[] cost = {3, 4, 3};
        int result = new CanCompleteCircuit().canCompleteCircuit(gas, cost);
        Assert.assertEquals(result, -1);
    }
}
